//
// Created by Crestimes on 24-6-2.
//

#include <sstream>
#include <iostream>
#include <string>
#include <cassert>

#include "global.h"
#include "ProductionManager.h"

ProductionManager::ProductionManager(const vector<string>& productionBuffs, const vector<string>& prodBuildTypeBuffs) {
    this->productionBuffs = productionBuffs;
    this->prodBuildTypeBuffs = prodBuildTypeBuffs;
    // 初始化productions成员变量
    initProductions();
    // 初始化nullableCharSet成员变量
    initNullableCharSet();
    // 初始化每个非终结符的First集合
    initCharFirstSet();
    // 初始化每个非终结符的Follow集合
    initCharFollowSet();
    // 初始化每条文法的expectationSet
    initExpectationSet();
}

/**
 * 计算文法语句的First_S集合
 * @param production 文法语句
 * @return 文法语句对应的First_S集合
 */
set<Character*> ProductionManager::calcFirstSSet(const Production& production) {
    set<Character*> result;
    for (const auto& c : production.right) {
        if (c->isEnd) {
            // 终结符
            if (c->name == NULL_CHARACTER) {
                // 如果是空字符串，跳过，继续
                continue;
            }
            result.insert(c);
            return result;
        }
        // else
        // 非终结符
        result.insert(c->firstSet.begin(), c->firstSet.end());
        if (!c->isNullable) {
            // 不可为空，直接结束
            return result;
        }
    }
    // 到这里说明该生成式right可以为空，需要加上左侧的Follow集合
    result.insert(production.left->followSet.begin(), production.left->followSet.end());
    return result;
}

/**
 * DFA图中节点文法引入非终结符的文法语句时，根据[引发引入行为的文法语句]中该非终结符后续的字符序列charsAfterN和[引发引入行为的文法语句]的expectationSet计算出[引入的文法语句]的expectationSet
 * @param charsAfterN [引发引入行为的文法语句]中该非终结符后续的字符序列
 * @param LastExpectationSet [引发引入行为的文法语句]的expectationSet
 * @return [引入的文法语句]的expectationSet
 */
set<Character*> ProductionManager::calcExpectationSet(const vector<Character*>& charsAfterN,
                                                      const set<Character*>& LastExpectationSet) {
    set<Character*> result;
    for (auto c : charsAfterN) {
        if (c->isEnd) {
            // 终结符
            if (c->name == NULL_CHARACTER) {
                // 如果是空字符串，跳过，继续
                continue;
            }
            result.insert(c);
            return result;
        }
        // else
        // 非终结符
        result.insert(c->firstSet.begin(), c->firstSet.end());
        if (!c->isNullable) {
            // 不可为空，直接结束
            return result;
        }
    }
    // 到这里说明该生成式right可以为空，需要加上上一个文法语句的expectationSet
    result.insert(LastExpectationSet.begin(), LastExpectationSet.end());
    return result;
}

/**
 * 解析buffs成员变量中的内容，初始化productions文法列表
 */
void ProductionManager::initProductions() {
    // 解析每行的数据
    stringstream prodStream;
    stringstream buildTypeStream;
    string prodStr, buildTypeStr;
    // 先把所有的左侧非终结符存入一个集合
    set<string> allNs;
    for (const auto& line : productionBuffs) {
        // 清空ss
        stringstream().swap(prodStream);
        prodStream << line;
        prodStream >> prodStr;
        allNs.insert(prodStr);
    }
    // 对每行进行处理
    size_t lineCount = min(productionBuffs.size(), prodBuildTypeBuffs.size());
    for (size_t i = 0; i < lineCount; i++) {
        // 清空ss
        stringstream().swap(prodStream);
        stringstream().swap(buildTypeStream);
        // 输入内容
        prodStream << productionBuffs[i];
        buildTypeStream << prodBuildTypeBuffs[i];
        // 第一个是左侧的非终结符
        prodStream >> prodStr;
        Character* left;
        // 先要判断该Character是否已经new过了，让同个Character只保留一份，内部变量修改时便于同步
        if (this->nameToCharacter.count(prodStr)) {
            left = this->nameToCharacter[prodStr];
        }
        else {
            left = new Character(prodStr);
            // 记得更新map
            this->nameToCharacter[prodStr] = left;
        }
        // 去除 ->
        prodStream >> prodStr;
        while (true) {
            vector<Character*> prodRight; // 右侧符号列表
            vector<int> buildTypeRight; // 右侧符号对应的建点操作列表
            while (true) {
                // 一直存入right，直到结尾或者|
                prodStream >> prodStr;
                buildTypeStream >> buildTypeStr;
                if (prodStr == "|") {
                    // 此时buildTypeStr也应该是"|"，否则就是配置文件写错了
                    assert(buildTypeStr == "|");
                    // 一份右侧符号序列已经完整
                    break;
                }
                // 保存建点操作类型
                buildTypeRight.emplace_back(stoi(buildTypeStr));
                // 保存Character
                // 先要判断该Character是否已经new过了，让同个Character只保留一份，内部变量修改时便于同步
                if (this->nameToCharacter.count(prodStr)) {
                    prodRight.emplace_back(this->nameToCharacter[prodStr]);
                }
                else {
                    // 根据字符串是否在allNs集合中判断该字符串是终结符还是非终结符
                    auto* ptr = new Character(prodStr, allNs.count(prodStr) == 0);
                    if (prodStr == NULL_CHARACTER) {
                        // 空作为终结符，但是在所有终结符的判断逻辑中会特判
                        ptr->isEnd = true;
                        ptr->isNullable = true;
                    }
                    prodRight.emplace_back(ptr);
                    // 更新map
                    this->nameToCharacter[prodStr] = ptr;
                }
                if (prodStream.eof()) {
                    // 不能和上面的|一起判断，eof需要存入后再break
                    break;
                }
            }
            // 构造文法语句
            // 文法语句下标从1开始，因为建立DFA图的时候会添加一条开始语句
            Production production(left, prodRight, static_cast<int>(this->productions.size() + 1), buildTypeRight);
            // 如果是 XXX -> .空 这种文法，直接让.到达最后，确保后续建立DFA图时所有引入了这个文法的点都可以直接规约
            if (production.right.size() == 1 && production.right[0]->name == NULL_CHARACTER) {
                production.pointIndex = 1;
            }
            // 保存文法语句
            this->productions.push_back(production);
            // 保存文法语句左侧非终结符对整个文法语句的映射
            nameToProductions[left->name].push_back(production);
            if (prodStream.eof()) {
                break;
            }
        }
    }
}

/**
 * 初始化可为空的非终结符集合nullableCharSet
 */
void ProductionManager::initNullableCharSet() {
    size_t size = this->nullableCharSet.size();
    while (true) {
        for (const auto& production : this->productions) {
            // 每一个文法语句
            // 判断是否right的所有字符都是nullable的，是的话左侧也可为空
            bool allNullableFlag = true;
            for (const auto& c : production.right) {
                if (!c->isNullable) {
                    allNullableFlag = false;
                    break;
                }
            }
            if (allNullableFlag) {
                production.left->isNullable = true;
                this->nullableCharSet.insert(production.left);
            }
        }
        if (size == this->nullableCharSet.size()) {
            // 不再增加就结束
            break;
        }
        size = this->nullableCharSet.size();
    }
}

/**
 * 为每个非终结符Character初始化First集合
 */
void ProductionManager::initCharFirstSet() {
    while (true) {
        bool changed = false;
        // 遍历每个文法语句
        for (const auto& production : this->productions) {
            const auto& left = production.left;
            // 遍历每个right中的Character
            for (auto c : production.right) {
                if (c->isEnd) {
                    if (c->name == NULL_CHARACTER) {
                        // 如果是空字符串，跳过，继续
                        continue;
                    }
                    // 终结符，存入First后break，该行文法语句的left的First求完了
                    const size_t preSize = left->firstSet.size();
                    left->firstSet.insert(c);
                    // 通过判断集合大小是否增加来判断本轮循环中是否有更新
                    if (preSize < left->firstSet.size()) {
                        changed = true;
                    }
                    break;
                }
                // else
                // 非终结符，取交集，你的First也是我的First
                // 通过判断集合大小是否增加来判断本轮循环中是否有更新
                const size_t preSize = left->firstSet.size();
                left->firstSet.insert(c->firstSet.begin(), c->firstSet.end());
                if (preSize < left->firstSet.size()) {
                    changed = true;
                }
                if (!c->isNullable) {
                    // 不为空也结束，为空可以继续for循环找下一个Character
                    break;
                }
            }
        }
        if (!changed) {
            break;
        }
    }
}

/**
 * 为每个非终结符Character初始化Follow集合
 */
void ProductionManager::initCharFollowSet() {
    while (true) {
        bool changed = false;
        // 遍历每个文法语句
        for (const auto& production : this->productions) {
            const auto& left = production.left;
            // temp记录当前左侧非终结符的Follow集合
            auto temp = left->followSet;
            // 遍历每个right中的Character
            // 需要逆序遍历
            for (auto c : vector<Character*>(production.right.rbegin(), production.right.rend())) {
                if (c->isEnd) {
                    if (c->name == NULL_CHARACTER) {
                        // 如果是空字符串，跳过，继续
                        continue;
                    }
                    // 遇到终结符，Follow集合不能合并，需要重新计算
                    set<Character*>().swap(temp);
                    // 将该终结符加入集合
                    temp.insert(c);
                }
                else {
                    // 非终结符
                    // 为该非终结符更新Follow集合
                    // 需要检测是否改变了集合
                    const size_t preSize = c->followSet.size();
                    c->followSet.insert(temp.begin(), temp.end());
                    if (preSize < c->followSet.size()) {
                        changed = true;
                    }
                    if (!c->isNullable) {
                        // 此非终结符不可为空，即当前的Follow集合(temp)无法向前传递，改为此非终结符的First集合
                        temp = c->firstSet;
                    }
                    else {
                        // 此非终结符可以为空，即当前的Follow集合(temp)可以向前传递，需要添加此非终结符的First集合
                        temp.insert(c->firstSet.begin(), c->firstSet.end());
                    }
                }
            }
        }
        if (!changed) {
            break;
        }
    }
}

/**
 * 初始化所有文法语句的expectationSet集合
 */
void ProductionManager::initExpectationSet() {
    for (auto production : productions) {
        production.expectationSet = calcFirstSSet(production);
    }
}
